package com.zyk.grate_offer.class02;

import java.util.HashMap;
import java.util.Map;

/**
 * 已知一个消息流会不断地吐出整数 1~N，
 * 但不一定按照顺序依次吐出
 * 如果上次打印的序号为i， 那么当i+1出现时
 * 请打印 i+1 及其之后接收过的并且连续的所有数
 * 直到1~N全部接收并打印完
 * 请设计这种接收并打印的结构
 *
 * @author zhangsan
 * @date 2021/4/23 11:32
 */
public class Code03_ReceiveAndPrintOrderLine {

    static class Node {
        String msg;
        Node next;

        public Node(String message) {
            msg = message;
        }
    }

    static class MessageBox {

        Map<Integer, Node> noHead;
        Map<Integer, Node> noEnd;
        int waitingIndex = 1;

        public MessageBox() {
            noHead = new HashMap<>();
            noEnd  = new HashMap<>();
        }

        public void push(int i, String message) {
            Node cur = new Node(message);
            // num~num
            noHead.put(i, cur);
            noEnd.put(i, cur);
            // 建立了num~num这个连续区间的头和尾
            // 查询有没有某个连续区间以num-1结尾
            if (noEnd.containsKey(i - 1)) {
                noEnd.get(i - 1).next = cur;
                noEnd.remove(i - 1);
                noHead.remove(i);
            }
            // 查询有没有某个连续区间以num+1开头的
            if (noHead.containsKey(i + 1)) {
                cur.next = noHead.get(i + 1);
                noEnd.remove(i);
                noHead.remove(i + 1);
            }

            if(i == waitingIndex) {
                print();
            }
        }

        public void print() {
            Node cur = noHead.get(waitingIndex);
            noHead.remove(waitingIndex);
            while (cur != null) {
                System.out.print(cur.msg);
                cur = cur.next;
                waitingIndex++;
            }
            noEnd.remove(waitingIndex-1);
            System.out.println();
        }

    }

    // for test
    public static void main(String[] args) {
        MessageBox mb = new MessageBox();
        mb.push(2, "B");
        mb.push(3, "C");
        mb.push(1, "A");

        mb.push(5, "E");
        mb.push(6, "F");
        mb.push(9, "I");
        mb.push(4, "D");

        mb.push(7, "G");
        mb.push(8, "H");
        mb.push(10, "J");
    }

}
